package com.dyz.swordFingerOffer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: daiyizheng
 * @date: 2021/6/11 21:49
 * @description:
 */
public class Serialize37 {

    String Serialize(TreeNode root) {
        //BFS 宽度搜说、
        if(root == null) {return "";}
        // 利用 StringBuilder构建一个可变的字符串对象，用于存放遍历二叉树的节点值
        StringBuilder sb = new StringBuilder();
        subSerialize(root, sb);
        // String内容是不可变的，StringBuilder内容是可变的，所以将StringBuilder对象转换成字符串
        return sb.toString();
    }

    StringBuilder subSerialize(TreeNode root, StringBuilder s) {
        if(root == null) {return s;}

        s.append(root.val).append("!");

        if(root.left != null) {
            subSerialize(root.left, s);
        }else {
            s.append("#!");
        }

        if(root.right != null) {
            subSerialize(root.right, s);
        }else {
            s.append("#!");
        }
        return s;
    }


    int index = 0;
    TreeNode Deserialize(String str) {
        if(str == null || str.length() == 0) {return null;}
        String[] sb = str.split("!");
        return subDeserialize(sb);
    }

    TreeNode subDeserialize(String[] strings) {
        if(strings[index].equals("#")) {
            index++; // 注意，此处index需要移动到下一位，对下一位进行判定
            return null;
        }

        // 构造完根节点 移动字符串数组的下标，准备构建根节点的左右子树
        TreeNode root = new TreeNode(Integer.parseInt(strings[index]));
        index++;

        root.left = subDeserialize(strings);
        root.right = subDeserialize(strings);

        return root;
    }
}
